﻿//#define _CRT_SECURE_NO_WARNINGS 1
////
////#include<stdio.h>
////#include<stdlib.h>
////
////void _TestMarge(int a[], int left, int right, int* ret)
////{
////	if (left >= right)
////		return;
////	
////	int mid = (left + right) >> 1;
////	_TestMarge(a, left, mid, ret);
////	_TestMarge(a, mid+1, right, ret);
////	
////	//开始归并
////	int begain1 = left;
////	int end1 = mid;
////	int begain2 = mid + 1;
////	int end2 = right;
////    
////	int index = left;
////	while (begain1 <= end1 && begain2 <= end2)
////	{
////		if (a[begain1] < a[begain2])
////		{
////			ret[index++] = a[begain1++];
////		}
////		else
////		{
////			ret[index++] = a[begain2++];
////		}
////	}
////
////	while (begain1 <= end1)
////	{
////		ret[index++] = a[begain1++];
////	}
////	while (begain2 <= end2)
////	{
////		ret[index++] = a[begain2++];
////	}
////
////	//拷贝回去
////	for (int i = left; i <= right; ++i)
////	{
////		a[i] = ret[i];
////	}
////}
////
////void TestMerge(int* a,int n)
////{
////	int* tmp = (int*)malloc(sizeof(int) * n);
////	_TestMarge(a, 0, n - 1, tmp);
////}
////
////void TestMergeSort()
////{
////	int a[] = { 10,6,7,1,3,9,4,2 };
////	int sz = sizeof(a) / sizeof(*a);
////
////	//并归排序
////	TestMerge(a,sz);
////	
////	int i = 0;
////	for (i = 0; i < sz; i++)
////	{
////		printf("%d ", a[i]);
////	}
////	
////}
////int main()
////{
////	TestMergeSort();
////	system("pause");
////	return 0;
////}
//
//
//
////#include<stdio.h>
////#include<stdlib.h>
////
////int main()
////{
////	int a[] = { 1,2,3,4,5, };
////	int sz = sizeof(a) / sizeof(a[0]);
////	int i = 0;
////	for (i = 0; i < sz; i++)
////	{
////		printf("%d , %s , %s , %s , lene:%d\n", a[i], __FILE__, __TIME__, __DATE__, __LINE__);
////	}
////	system("pause");
////	return 0;
////}
//
//
//#include<stdio.h>
//#include<stdlib.h>
//
////int main()
////{
////	printf("%d\n", __STDC__);
////	system("pause");
////	return 0;
////}
//
////#define MAX 100
////int main()
////{
////	printf("%d", MAX);
////	int a[MAX] = { 0 };
////	return 0;
////}
//
//
//
//#define DEBUG_PRINT printf("file:%s\tline:%d\t \
//                          date:%s\ttime:%s\n" ,\
//                          __FILE__,__LINE__ ,  \
//                          __DATE__,__TIME__ )  
//
//
////#define SQUABE(x) x * x
////
////int main()
////{
////	printf("%d", SUL(1 + 7));
////	return 0;
////}
//
//
//
////#include<stdio.h>
//// int main()
//// {
////     int a = 10;
////     printf("the value of a is %d\n", a);
////
////     int b = 20;
////     printf("the value of b is %d\n", b);
////
////     float f = 3.14f;
////     printf("the value of f is %f\n", f);
////
////     return 0;
//// }
//
// //int main()
// //{
// //    printf("hello world\n");
// //    printf("hello " "world\n");
// //    system("pause");
// //    return 0;
// //}
//
//
// //#define print_format(num, format) \
// //            printf("the value of "#num" is "format, num)
//
// //int main()
// //{
// //    int a = 10;
// //    print_format(a, "%d\n");
// //    //printf("the value of a is %d\n", a);
//
// //    int b = 20;
// //    print_format(b, "%d\n");
// //    //printf("the value of b is %d\n", b);
//
// //    float f = 3.14f;
// //    print_format(f, "%f\n");
// //    //printf("the value of f is %f\n", f);
//
// //    system("pause");
// //    return 0;
// //}
//
//
// //int Class110 = 2023;
//
// //#define CAT(x,y) x##y
// ////Class110
// //int main()
// //{
// //    printf("%d\n", CAT(Class, 110));
//
// //    system("pause");
// //    return 0;
// //}
//
//
//
//
//int Max(int x, int y)
//{
//    return x > y ? x : y;
//}
//
//
//int main()
//{
//    int a = 3;
//    int b = 5;
//    int c = Max(a++, b++);
//    printf("%d\n", c);
//    printf("%d\n", a);
//    printf("%d\n", b);
//    system("pause");
//    return 0;
//}

#include<stdio.h>
#include<stdlib.h>

//插入排序
void InsertSort(int a[], int sz)
{
	int i = 0;
	for (i = 0; i < sz - 1; i++)
	{
		int begain = i;
		int end = a[begain + 1];
		while (begain >= 0)
		{
			if (a[begain] > end)
			{
				a[begain + 1] = a[begain];
				begain--;
			}
			else
			{
				break;
			}
		}
		a[begain+1] = end;
	}
}


void Swaq(int* a, int* b)
{
	int tmp = *a;
	*a = *b;
	*b = tmp;
}

//三木取中
int IndexMid(int a[], int left, int right)
{
	int mid = (left + right) >> 1;
	if (a[left] > a[mid])
	{
		if (a[mid] > a[right])
			return mid;
		else if (a[right] > a[left])
			return left;
		else
			return right;
	}
	else //a[mid] > a[left]
	{
		if (a[left] > a[right])
			return left;
		else if (a[right] > a[mid])
			return mid;
		else
			return right;
	}
}

//挖坑法
//int part1(int a[], int left, int right)
//{
//	//三木取中
//	int mid = IndexMid(a, left, right);
//	Swaq(&a[left], &a[mid]);
//	int begain = left;
//	int end = right;
//	int key = a[left];
//	int pvint = left;
//
//	while (begain < end)
//	{
//		//先找小到左边坑位那里
//		while (begain < end && a[end] >= key)
//		{
//			end--;
//		}
//		a[pvint] = a[end];
//		pvint = end;
//
//		//找大放到右边坑位
//		while (begain < end && a[begain] <= key)
//		{
//			++begain;
//		}
//		a[pvint] = a[begain];
//		pvint = begain;
//	}
//	pvint = begain;
//	a[pvint] = key;
//
//	return pvint;
//}

//左右指针挖坑法
int part2(int a[], int left, int right)
{
	//三木取中
	int mid = IndexMid(a, left, right);
	Swaq(&a[left], &a[mid]);
	
	int begain = left;
	int end = right;
	int key = a[left];
	while (begain < end)
	{
		//找小
		while (a[end] >= key && begain < end)
		{
			--end;
		}

		//找大
		while (a[begain] <= key && begain < end)
		{
			++begain;
		}
        
		Swaq(&a[end], &a[begain]);
	}
	Swaq(&a[begain], &key);
	return begain;
}

//前后指针法
int part3(int a[], int left, int right)
{
	//三木取中
	int mid = IndexMid(a, left, right);
	Swaq(&a[left], &a[mid]);
	int key = a[left];
	int prev = left;
	int cur = prev+1;
	while (cur <= right )
	{
		while (a[cur] <= key &&  prev!= cur)
		{
			Swaq(&a[prev], &a[cur]);
			prev++;
		}
		cur++;
	}
	Swaq(&a[prev], &key);
	return prev;
}
//快速排序挖坑法
void QuickSort(int a[], int left, int right)
{
	if (left >= right)
		return;

	
	int pvint = part3(a, left, right);

	//小区间优化
	if (pvint - 1 - left > 10)
	{
		QuickSort(a, left, pvint - 1);
	}
	else
	{
		InsertSort(a, pvint - 1 - left + 1);
	}
	if (right - pvint + 1 > 10)
	{
		QuickSort(a, pvint + 1, right);
	}
	else
	{
		InsertSort(a+ pvint + 1, right - pvint - 1 + 1);
	}
}


void TestQuickSort()
{
	int a[] = { 5,3,2,7,8,6,5,0,9,4 };
	int sz = sizeof(a) / sizeof(*a);
	QuickSort(a, 0, sz-1);
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", a[i]);
	}
}

void _MargeSort(int a[], int left, int right, int tmp[])

 {
	if (left >= right)
		return;
	int mid = (left + right) >> 1;
	_MargeSort(a , left, mid, tmp);
	_MargeSort(a , mid+1, right, tmp);
	
	int begain1 = left;
	int end1 = mid ;
	int begain2 = mid + 1;
	int end2 = right;
	int Index = left;
	while (begain1 <= end1 && begain2 <= end2)
	{
		if (a[begain1] > a[begain2])
		{
			tmp[Index++] = a[begain2++];
		}
		else
		{
			tmp[Index++] = a[begain1++];
		}
	}
	while (begain1 <= end1)
	{
		tmp[Index++] = a[begain1++];
	}
	while (begain2 <= end2)
	{
		tmp[Index++] = a[begain2++];
	}

	int i = left;
	for (i = left; i <= right; i++)
	{
		a[i] = tmp[i];
	}
}

void MargeSort(int a[], int sz)
{
	int* tmp = (int*)malloc(sizeof(int) * sz);
	_MargeSort(a,0,sz-1,tmp);
}
void TestMergeSort()
{
	int a[] = { 10,6,7,1,3,9,4,2 };
	int sz = sizeof(a) / sizeof(*a);
	MargeSort(a,sz );
	int i = 0;
	for (i = 0; i < sz; i++)
	{
		printf("%d ", a[i]);
	}
}
int main()
{
	//三种快速方法
	//TestQuickSort();

	//归并排序
	TestMergeSort();
	system("pause");
	return 0;
}